package algo.A05_其他排序算法;

import util.ArrayUtil;

import java.util.Arrays;

/**
 * 给定以排序的数组，不重复打印数组中所有相加和为K的不降序二元组
 * 例：arr = {-8，-4，-3,0,2,4,5,8,9,10}，K = 10
 * 上述题目的意思是找出两两相加等于10的元素，将他们打印出来
 * 输出（0,10）（2,8）
 * <p>
 * 双指针法
 */
public class T01_排序数组中找和的因子 {
    public static void main(String[] args) {
        int[] arr = ArrayUtil.getRandomArrWithoutRepetition(10, -10, 20);
        Arrays.sort(arr);
        ArrayUtil.print(arr);
        solution(arr,10);
    }

    /**
     * 双指针，左右相加，小于k说明左边小了，左指针往后移动，大于k说明右边大了，右指针往前移动
     * @param arr
     * @param k
     */
    private static void solution(int[] arr, int k) {
        int left = 0;
        int right = arr.length - 1;
        while (left < right) {
            if (arr[left] + arr[right] == k) {
                System.out.println("(" + arr[left] + "," + arr[right] + ")");
                left++;
            }else if (arr[left] + arr[right] < k) {
                left++;
            }else {
                right--;
            }
        }
    }
}
